#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW 0
#define ElemType int
#define Status int

// 定义链表节点结构体
typedef struct LNode {
    ElemType data;  // 数据域
    struct LNode *next;  // 指针域
} LNode, *LinkList;

// 初始化链表
LinkList InitList() {
    LNode *L = (LNode *)malloc(sizeof(LNode));  // 分配头节点空间
    if (L == NULL) {  // 内存分配失败
        return NULL;
    }
    L->next = NULL;  // 头节点的指针域置空
    return L;  // 返回头节点指针
}

// 插入元素
Status ListInsert(LinkList L, int i, ElemType e) {
    if(L == NULL) {  // 链表不存在
        return ERROR;
    }
    if(i<1){  // i值不合法
        return ERROR;   
    }
    LNode *p = L;
    int j = 0;
    while(p!=NULL && j<i-1){
        p = p->next;  // 查找第i-1个节点
        j++;
    }
    if(p==NULL){  // i值不合法
        return ERROR;
    }
    LNode* newNode = (LNode*)malloc(sizeof(LNode));// 分配新节点空间
    if(newNode==NULL){// 内存分配失败
        return ERROR;
    }
    newNode->data = e;// 新节点的数据域赋值为e
    newNode ->next = p->next;   // 新节点的指针域指向第i个节点
    p->next = newNode;
    return OK;
}
// 删除元素
ElemType LinkListDelete(LinkList L, int i,ElemType e){
    if(L == NULL){// 链表不存在
        return ERROR;
    }
     if(i<1){  // i值不合法
        return ERROR;   
    }
    LNode * p= L;// 指针p指向头节点
    int j = 0;
    while(p!=NULL && j<i-1){// 查找第i-1个节点
        p = p->next;
        j++;
    }
    if(p==NULL){// i值不合法
        return ERROR;
    }
    LNode * q = p->next;// 指针q指向第i个节点
    if(q==NULL){// i值不合法
        return ERROR;
    }
    p->next = q->next;// 第i-1个节点的指针域指向第i+1个节点
    e = q->data;// 保存被删除节点的数据域
    free(q);// 释放第i个节点的空间
    return e;
}
// 查找元素位置序号
int LocateElem(LinkList L, ElemType e) {
    if(L == NULL) {  // 链表不存在
        return ERROR;
    }
    
    LNode* p = L->next;  // 指针p指向第一个节点
    int i = 1;  // 计数器
    while(p!=NULL && p->data!=e){  // 查找元素e
        p = p->next;  // 指针p后移
        i++;  // 计数器加一
    }
    if(p==NULL){  // 未找到元素e
        return ERROR;
    }
    return i;  // 返回元素e的位置
}
// 查找位置的元素
ElemType GetElem(LinkList L, int i) {
    if(L == NULL){// 链表不存在
        return ERROR;
    }
     if(i<1){  // i值不合法
        return ERROR;   
    }
    LNode *p = L ;
    int j = 1;// 计数器
    while(p!=NULL && j<i-1){// 查找第i个节点
        p = p->next;
        j++;
    }
    if(p==NULL){// i值不合法
        return ERROR;
    }
    return p->next->data;// 返回第i个节点的数据域
}
// 打印链表
void PrintList(LinkList L) {
    if(L == NULL) {  // 链表不存在
        return;
    }
    LNode *p = L->next;  // 指针p指向第一个节点
    while(p!=NULL) {  // 遍历链表
        printf("%d ", p->data);  // 打印节点的数据域
        p = p->next;  // 指针p后移
    }
    printf("\t");  // 换行
    
}
// 销毁链表
void DestroyList(LinkList L) {
    if(L == NULL) {  // 链表不存在
        return;
    }
    LNode *p = L->next;  // 指针p指向第一个节点
    while(p!=NULL) {  // 遍历链表
        LNode *q = p->next;  // 指针q指向p的下一个节点
        free(p);  // 释放p所指向的节点
        p = q;  // 指针p后移
    }
    free(L);  // 释放头节点
}
int main() {
    LinkList L = InitList();  // 初始化链表
    int i, e;
    while(1) {  // 循环执行
        printf("请输入操作类型（1：插入元素，2：删除元素，3：查找元素位置序号，4：查找位置的元素，5：打印链表，0：退出）：");
        scanf("%d", &i);  // 输入操作类型
        if(i==0) {  // 退出循环
            break;
        
        } else if(i==1) {  // 插入元素
            printf("请输入插入位置和元素值：");
            
            scanf("%d %d", &i, &e);  // 输入插入位置和元素值}
            if(ListInsert(L, i, e)==OK) {  // 插入元素
                printf("插入成功\n");
            } else {  // 插入失败
                printf("插入失败\n");
            }
        } else if(i==2) {  // 删除元素
            printf("请输入删除位置：");
            scanf("%d", &i);  // 输入删除位置
            if(LinkListDelete(L, i,e)==OK) {  // 删除元素
                printf("删除成功\n");
            } else {  // 删除失败
                printf("删除失败\n");
            }
        } else if(i==3) {  // 查找元素位置序号
            printf("请输入要查找的元素值：");
            scanf("%d", &e);  // 输入要查找的元素值
            int pos = LocateElem(L, e);  // 查找元素位置序号
            if(pos==ERROR) {  // 未找到元素
                printf("未找到元素\n");
            } else {  // 找到元素
                printf("元素位置序号为：%d\n", pos);
            }
        } else if(i==4) {  // 查找位置的元素
            printf("请输入要查找的位置：");
            scanf("%d", &i);  // 输入要查找的位置
            e = GetElem(L, i);  // 查找位置的元素
            if(e==ERROR) {  // 未找到元素
                printf("未找到元素\n"); // 输出错误信息
            } else {  // 找到元素
                printf("元素值为：%d\n", e);  // 输出元素值
            }            } else if(i==5) {  // 打印链表
            PrintList(L);  // 打印链表
        } else {  // 输入错误
            printf("输入错误\n");  // 输出错误信息
        }
    }   
    DestroyList(L);  // 销毁链表    
    return 0;
}